import java.text.DateFormat;
import java.util.Date;
import java.util.Random;

public class SortQuick {
    public static void QuickSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        QuickSortCore(arr, 0, arr.length - 1);
    }

    public static void QuickSortCore(int[] arr, int lo, int hi) {
        if (lo < hi) {
            int mid = Partition(arr, lo, hi); // divide array to two parts
            QuickSortCore(arr, lo, mid - 1); // sorted left part
            QuickSortCore(arr, mid + 1, hi); // sorted right part
        }
    }

    public static int Partition(int[] arr, int lo, int hi) {
        // random swap reduce rate of baddest case appear
        int index = lo + (int) (Math.random() * (hi - lo + 1));
        swap(arr, index, hi);
        // divide original array to smaller and equal or bigger two part
        // small指向小于pivot的最后一个数索引
        int small = lo - 1;
        while (lo < hi) {
            if (arr[lo] < arr[hi]) {
                small++;
                swap(arr, small, lo);
            }
            lo++;
        }
        // put pivot into middle
        small++;
        swap(arr, small, hi);

        // return middle position
        return small;
    }

    // swap array element in i and j
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[1000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = new Random().nextInt() * 1000000;
        }
        long start = System.currentTimeMillis();
        QuickSort(arr);
        long end = System.currentTimeMillis();
        for (int value : arr) {
            System.out.println(value);
        }
        System.out.print("花费了：" + (end - start) + "ms");
    }
}

